package top.pro51.guide.chapter1;

import java.util.LinkedList;

public class 生成窗口最大值数组 {
    public static int[] getMaxWindow(int arr[], int w) {
        //判空 运行条件
        if (arr == null || arr.length < w || w < 1) {
            return null;
        }

        //双端队列记录窗口中最大值下标
        LinkedList<Integer> qmax = new LinkedList<>();
        //记录结果的数组长度
        int[] res = new int[arr.length - w + 1];
        int index = 0;
        for (int i = 0; i < arr.length; i++) {

            while (!qmax.isEmpty() && arr[qmax.peekLast()] <= arr[i]) {
                qmax.pollLast();
            }
            qmax.addLast(i);

            //过期计算
            if (qmax.peekFirst() == i - w) {
                qmax.pollFirst();
            }

            //记录结果res[]
            if (i >= w - 1) {
                res[index++] = arr[qmax.peekFirst()];
            }
        }
        return res;
    }

    public static void main(String[] args) {
        int[] arr = new int[]{4, 3, 5, 4, 3, 3, 6, 7};
        int[] res = getMaxWindow(arr, 3);
        for (int r : res) {
            System.out.println("窗口中最大值为 " + r);
        }
    }
}
